package solution.liuyu2783.offer;

import java.util.ArrayList;

/**
 * 剑指 Offer 17. 打印从1到最大的n位数
 *
 */
public class Q17_MaxNum_M {


	static ArrayList<String> arrayList = new ArrayList();
	
	public static void main(String[] args) {
		StringBuilder sb = new StringBuilder();
		int[] data = {1,2,3};
		dfs(data, sb);
		System.out.println("结果："+ arrayList.toString());
	}
	
	/**
	 * 思路：全排序
	 */
	public static void dfs(int[] data, StringBuilder path) {
		//递归终止条件
		if(data.length == path.length()) {
			System.out.println("打印路径："+ path.toString());
			arrayList.add(path.toString());
			return;
		}
		for(int i = 0; i < data.length; i++) {
			int temp = data[i];
			if(temp == -1) { //用-1占位，表示已经走过
				System.out.println("已过："+ path.toString()+", 当前数字：data["+i+"] = "+temp);
				continue;
			}
			path.append(temp);
			System.out.println("路径："+ path.toString()+", 当前数字：data["+i+"] = "+temp);
			data[i] = -1; //使用过的，需要标记一下
			dfs(data, path);
			//回溯
			path.deleteCharAt(path.length() - 1);//将path回溯，使得每次i获得的path是相同的
			data[i] = temp; //data[i]也需要还原
		}
	}
}
